Practice Problems and Solutions 2 A

These problems are offered to help understand the lecture material and assist with completing homeworks; they will also form the basis for some problems on the midterms. They are entirely optional, and feel free to skip if you understand a concept!

You should do these problems on paper or mentally first, and only THEN check the solution.

This set of problems uses Bare-Bones Haskell, with explicit data declarations for Pairs and Lists; here is a version of the same problems with the built-in Haskell notations for tuples and lists.

2. BareBones Haskell: Types and type checking

Consider the following data declaration:

data D a = A Integer | B Bool | C a 
data Nat = Zero | Succ Nat
data Pair a b = P a b
data List a = Nil | Cons a (List a)
data Tree a = Null | Node (Tree a) a (Tree a)

 

For the first part of these exercises, we will ask you to give the types of various constructors in the above data declarations; then we will define some functions using these data, plus Integer and Bool, and you will need to give the types of the functions, as well as some expressions involving these functions.

We assume that we can have Integer and Bools as defined in the Haskell Prelude. Assume for the purposes of these exercises that all arithmetic operators operate only on Integers, so pretend the type of (+) is:

 (+): Integer -> Integer -> Integer.

If the expression is an error, explain where the error occurs.

Constructors

Give the type of the following constructors.

2.1. Zero

Show Solution

Zero :: Nat

Hint: You can check the type of expressions and symbols by using
the following:

Main> :type Zero       -- can also use the abbreviation  :t
Zero :: Nat

2.2. Succ

Show Solution

Succ :: Nat -> Nat

2.3. B

Show Solution

B :: Bool -> D a

2.4. C

Show Solution

C :: a -> D a

2.5. Cons

Show Solution

Cons :: a -> List a -> List a    

2.6. P

Show Solution

P :: a -> b -> Pair a b

2.7. Node

Show Solution

Node :: Tree a -> a -> Tree a -> Tree a

Constructor Expressions (with Integer and Bool)

Give the type of the following expressions

2.8. (Succ Zero)

Show Solution

(Succ Zero) :: Nat    		

2.9. C 6

Show Solution

C 6 :: C Integer

Note that if you try this in the REPL, you will get:

*Main> :t C 9
C 9 :: Num a => D a

which says that a can be any "numeric type". We will talk
about what this means when we study type classes. For
this set of exercises, we will assume that all such
types are simple Integer, hence our answer. 
 

2.10. P 5 True

Show Solution

P 5 True  :: Pair Integer Bool    

2.12. C (P 4 (A 5))

Show Solution

C (P 4 (A 5)) :: D (Pair Integer (D a2))

2.12. C (C (B True))

Show Solution

C (C (B True)) :: D (D (D a)) 

2.13. P (P 9 (Succ Zero)) (P (C Zero) True)

Show Solution

P (P 9 (Succ Zero)) (P (C Zero) True) :: Pair (Pair Integer Nat) (Pair (D Nat) Bool)

2.14. (Cons (C 4) (Cons (A 5) Nil))

Show Solution

(Cons (C 4) (Cons (A 5) Nil)) :: List (D Integer)

2.15. (Cons (Cons True Nil) Nil)

Show Solution

(Cons (Cons True Nil) Nil) :: List (List Bool)

2.16. Node Null (Cons (Succ (Succ Zero)) Nil) Null

Show Solution

Node Null (Cons (Succ (Succ Zero)) Nil) Null :: Tree (List Nat)

2.17. C (Node Null (Cons (C (P 3 Zero)) Nil) Null)

Show Solution

C (Node Null (Cons (C (P 3 Zero)) Nil) Null) :: D (Tree (List (D (Pair Integer Nat))))

Types Involving Constructors and Functions

Suppose for this section that in addition to the data declarations above, we have the following data and function definitions. (The types Either and Maybe are defined in the Prelude and used very often in Haskell programming.)

data Either a b = Left a | Right b
data Maybe a = Nothing | Just a

safeHead Nil        = Nothing
safeHead (Cons x _) = Just x

safeTail  Nil        = Nothing
safeTail (Cons _ xs) = Just xs

fst (P x _) = x
snd (P _ y) = y

f (P x y) = x + y

g (P True x) = Left x
g (P False y) = Right y

h Zero = 0
h (Succ x) = 1 + (h x)

2.18. f

Show Solution

2.19. g

Show Solution

g :: Pair Bool b -> Either b b

2.20. h:

Show Solution

h :: Nat -> Integer 

2.21. safeHead

Show Solution

safeHead :: List a -> Maybe a

2.22. safeTail

Show Solution

safeTail :: List a -> Maybe (List a)

2.23. fst

Show Solution

fst :: P a b -> a

2.24. snd

Show Solution

snd :: P a b -> b

Give the types of the following expressions. If the expression can not be typed, explain why.

2.25. g (P (not True) (f (P 4 5)))

Show Solution

g (P (not True) (f (P 4 5))) :: Either Integer Integer

2.26. fst (P (h Zero) (g (P True True))))

Show Solution

fst (P (h Zero) (g (P True True)))) :: Integer
	 

2.27. safeHead (Cons (fst (P 3 True)) (Cons (h Zero) Nil))

Show Solution

safeHead (Cons (fst (P 3 True)) (Cons (h Zero) Nil)) :: Maybe Integer

2.28. safeHead (safeTail (Cons (fst (P 3 True)) (Cons (h Zero) Nil)))

Show Solution

The expression can not be typed. The expression

(safeTail (Cons (fst (P 3 True)) (Cons (h Zero) Nil)))

has type 

Maybe (List Integer)

and safeHead requires a (List a). 

2.29.

 g (P (fst x) (snd x))
      where x = (P (snd (P 3 True)) (P False 5))   

Show Solution

The expression has type Either (Pair Bool Integer) (Pair Bool Integer)

2.30.

 g (P (snd x) (fst x))
      where x = (P (snd (P 3 True)) (P False 5))   

Show Solution

No, it doesn't type check: the expression (snd x) has
type

Pair Bool Integer

and g expects a type (P Bool a), and (Pair Bool Integer) is not the same as Bool. 

2.31.

 g (P (fst x) (fst x))
      where x = (P (snd (P 3 True)) (P False 5))   

Show Solution

The expression has type  Either Bool Bool.